FIG. 1 illustrates an exemplary database 30 storing a range partitioned database table 31 that is partitioned into six (6) one-column partitions. A partition 0 has a starting value of 1 and an ending value of 20. A partition 1 has a starting value of 21 and an ending value of 40. A partition 2 has a starting value of 41 and an ending value of 60. A partition 3 has a starting value of 61 and an ending value of 80. A partition 4 has a starting value of 81 and an ending value of 100. A partition 5 has a starting value of 121 and an ending value of infinity ∞. A hole (not shown) between partitions 4 and 5 has a starting value of 101 and an end value of 120.
A binary search of table 31 is performed whenever there is a need to determine which of the partitions 0-5 of table 31 a particular key falls in given the logical range of each partition 0-5. Specifically, a binary search of table 31 involves repeatedly dividing table 31 in two, and searching the half that is known to contain the key. For example, with the key being 42, table 31 would be initially divided in two with a first half of 1-80 and second half of 81-infinity, and an initial comparison of the key 42 to the two halves would result in a subsequent search of the first half 1-80 and a discarding of the second half 81-∞. Thereafter, the first half 1-80 would be divided by two into a third half 1-40 and a fourth half 41-80, and a comparison of key 42 to the two halves would result in a discarding of the third half 1-40 and a subsequent search of the fourth half 41-80. Finally, the fourth half 41-80 would be divided by two into a fifth half 41-60 and a sixth half 61-80, and a comparison of key 42 to the two halves would result in a finding of key 42 in the fifth half 41-60, which is partition 2.
The exemplary binary search of table 31 would occur at runtime. As such, the processing time for performing the binary search of table 31 can be costly in terms of system performance, particularly in view of having to divide table 31 within the hole including logical range 101 to 120, or within partition 5 having an infinite end value. Moreover, the cost of performing the binary search of table 31 at runtime could significantly increase if table 31 had multiple columns.
A challenge therefore for the computer industry is to develop a technique for performing a binary search of a range partitioned database table (e.g., table 31) in a timely manner that does not considerably affect the overall performance of the system performing such a search of the range partitioned database table.